import java.util.*;

public class Test {
    /*
    双指针
     */
    /*
    题目 1：验证回文串
     */
    // 还有数字！！
    public boolean isNumAlpha(char x){
        if(x >= 'a' && x <= 'z' || x >= '0' && x <= '9'){
            return true;
        }
        return false;
    }
    public boolean isPalindrome(String ss1) {
        String ss = ss1.toLowerCase();
        char[] s = ss.toCharArray();

        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            while(left < right && !isNumAlpha(s[left])){
                left++;
            }

            while(left < right && !isNumAlpha(s[right])){
                right--;;
            }

            if(left < right){
                if(s[left] != s[right]){
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }

    /*
    题目 2：反转字符串Ⅱ
     */
    public void reverse(char[] arr, int i, int j){
        while(i < j){
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    public String reverseStr(String ss, int k) {
        char[] s = ss.toCharArray();
        int n = s.length;

        for(int i = 0; i < n; i += 2 * k){
            if(i + k - 1 < n){
                reverse(s, i, i + k - 1);
            }else{
                reverse(s, i, n - 1);
            }
            // 可简化成
            // reverse(s, i, Math.min(i + k, n) - 1);
        }

        return new String(s);

    }

    /*
    题目 3：验证回文串 Ⅱ
     */
    public boolean validPalindrome(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            if(s[left] == s[right]){
                left++;
                right--;
            }else{
                return subValidPalindrome(s, left + 1, right) || subValidPalindrome(s, left, right - 1);
            }
        }
        return true;


    }

    public boolean subValidPalindrome(char[] arr, int left, int right){
        while(left < right){
            if(arr[left] == arr[right]){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }

    /*
    题目 4 ：反转字符串中的元音字母
     */
    public String reverseVowels(String ss) {
        char[] vowels = {'a','e','i','o','u','A','E','I','O','U'};
        Set<Character> set = new HashSet<>();
        for(char vowel : vowels){
            set.add(vowel);
        }
        char[] s = ss.toCharArray();
        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            while(left < right && !set.contains(s[left])){
                left++;
            }

            while(left < right && !set.contains(s[right])){
                right--;
            }

            reverse1(s, left++, right--);
        }

        return new String(s);
    }

    public void reverse1(char[] arr, int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /*
    题目5：反转字符串中的单词 Ⅲ
     */
    public String reverseWords(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;

        int left = 0;
        int right = 0;

        while(right < n){
            while(right < n && s[right] != ' '){
                right++;
            }

            reverse2(s, left, right - 1);

            if(right < n){
                right++;
                left = right;
            }
        }

        return new String(s);

    }

    public void reverse2(char[] arr, int i, int j){
        while(i < j){
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }

    }

    /*
    题目 6：判断子序列
     */
    public boolean isSubsequence(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t= tt.toCharArray();
        int lens = s.length;
        int lent = t.length;

        int i = 0;
        int j = 0;

        while(i < lent && j < lens){

            if(s[j] == t[i]){
                i++;
                j++;
            }else{
                i++;
            }
        }

        return j == lens;

    }

    /*
    题目 7：按奇偶排序数组 Ⅱ
     */
    public int[] sortArrayByParityII1(int[] nums) {
        int n = nums.length;

        int l = 0;
        int r = 1;

        while(l < n - 1 && r < n){
            while(l < n - 1 && (nums[l] % 2 == 0)){
                l += 2;
            }

            while(r < n && (nums[r] % 2 == 1)){
                r += 2;
            }

            if(l < n - 1 && r < n){
                int temp = nums[l] ;
                nums[l] = nums[r];
                nums[r] = temp;
            }

            l += 2;
            r += 2;
        }
        return nums;
    }

    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;

        int j = 1;
        for(int i = 0; i < n - 1; i += 2){
            if(nums[i] % 2 == 1){
                while(nums[j] % 2 == 1){
                    j += 2;
                }
                swap(nums, i , j);
            }

        }
        return nums;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
    题目 8 ：最小公共值
     */
    public int getCommon(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int i = 0;
        int j = 0;

        while(i < n && j < m){
            if(nums1[i] < nums2[j]){
                i++;
            }else if(nums1[i] > nums2[j]){
                j++;
            }else{
                return nums2[j];
            }
        }
        return -1;
    }


}
